package com.mango.leet.code.week1.game283;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
 * 6018. 根据描述创建二叉树
 */

/**
 * 给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
 *
 * 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
 * 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。
 * 请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
 *
 * 测试用例会保证可以构造出 有效 的二叉树。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
 * 输出：[50,20,80,15,17,19]
 * 解释：根节点是值为 50 的节点，因为它没有父节点。
 * 结果二叉树如上图所示。
 * 示例 2：
 *
 *
 *
 * 输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
 * 输出：[1,2,null,null,3,4]
 * 解释：根节点是值为 1 的节点，因为它没有父节点。
 * 结果二叉树如上图所示。
 *  
 *
 * 提示：
 *
 * 1 <= descriptions.length <= 104
 * descriptions[i].length == 3
 * 1 <= parenti, childi <= 105
 * 0 <= isLefti <= 1
 * descriptions 所描述的二叉树是一棵有效二叉树
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/create-binary-tree-from-descriptions
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC6018 {
    /**
     * Definition for a binary tree node.
     **/
     public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
        public TreeNode createBinaryTree(int[][] descriptions) {
            // map用来存节点索引
            Map<Integer,TreeNode> nodeMap = new HashMap<>();
            // set用来存
            Set<Integer> childSet = new HashSet<>();
            for(int[] node : descriptions){
                int p = node[0], c = node[1], left = node[2];
                // 1. 先保存节点到map中
                if(!nodeMap.containsKey(p)) {
                    nodeMap.put(p, new TreeNode(p));
                }
                if(!nodeMap.containsKey(c)) {
                    nodeMap.put(c, new TreeNode(c));
                }
                // 2. 如果是左节点，则放到父节点的left
                if(left == 1){
                    nodeMap.get(p).left = nodeMap.get(c);
                }else{
                    // 如果是右节点，则放到父节点的right
                    nodeMap.get(p).right = nodeMap.get(c);
                }
                // 3. 将子节点放到set中，用于查找父节点的
                childSet.add(c);
            }
            // 4. 循环节点，找到不在子节点中的节点，就是根节点并返回
            for(int child : nodeMap.keySet()){
                if(!childSet.contains(child)){
                    return nodeMap.get(child);
                }
            }
            return null;
        }
    }
}
/**
 * 2022-03-06
 * 思路：
 * 1. 先保存节点到map中
 * 2. 如果是左节点，则放到父节点的left； 如果是右节点，则放到父节点的right
 * 3. 将子节点放到set中，用于查找父节点的
 * 4. 循环节点map，找到不在子节点中的节点，就是根节点并返回
 */
